The present invention relates to asymmetric key-code cryptographic communications systems and methods and in particular to systems and methods involving the co-operative generation of public parameters in such a way that co-operative decryption is required.
With the increase in accessibility to microprocessors, for example in the form of programmable computers or dedicated microprocessors, the transfer of information between microprocessors, over a communications channel, has rapidly increased. There are many applications, for example electronic banking, e-mail systems and subscriber information systems, where it is preferable to encrypt any information which will pass over the communications channel in order to prevent its disclosure to unauthorised recipients.
To implement cryptographic functions in a microprocessor controlled communications system symmetrical or asymmetrical algorithms may be used. Functions based on asymmetrical algorithms are particularly useful since a user, for example a first microprocessor, can generate and make universally available a single xe2x80x9cpublicxe2x80x9d encryption key to anyone, for example a second microprocessor, wishing to send the user a message. The user can then retain a xe2x80x9cprivatexe2x80x9d, different decryption key which is related in some way to the public key. One such asymmetrical algorithm that is used in cryptographic communications systems is the well known RSA algorithm (U.S. Pat. No. 4,405,829).
The parameters for the well known RSA system consist of a public modulus N which is a product of two primes; P, Q, a public encryption key e; and a secret decryption key d. The factorisation of N is a secret parameter and the keys are related by a formula of the form de=1 mod xcfx86(N), where xcfx86(N) is the order of the multiplicative group of integers modulo N. Then with knowledge of only the public parameters, any message (so called xe2x80x9cplaintextxe2x80x9d message), x (represented as a positive integer less than N), can be enciphered using a formula of the formy y=xe mod N. The secret parameter d is needed to decipher the encrypted message (so called xe2x80x9cciphertextxe2x80x9d message), y, via a formula of the form x=yd mod N.
Thus, in the known asymmetrical cryptographic systems the user is in possession of the only decryption key and can act autonomously to decrypt any message. This may be a problem, for example in circumstances where a central authority regulates, generates and issues public and private keys then this central authority has the capability to masquerade as any user-microprocessor and decrypt private messages.
A cryptographic method involving a split-key decryption scheme is described by Boneh and Franklin (Efficient Generation of Shared RSA Keys, to be presented at CRYPTO ""97, University of California Aug. 17-21, 1997, published by Springer Verlag and currently available at the web site location http://www.cs.princeton.edu/xcx9cdabo/publications.htmlxe2x80x94Lecture Notes in Computer Science vol 1294). However this describes a scheme involving three entities in generating the split-key, any two of which can co-operate to decrypt a message without recourse to the third.
It is the object of the present invention to provide a cryptographic communications system and a cryptographic method for use in such a system that requires the co-operative effort of only two entities but which can be expanded for application by a plurality of entities all of whom must co-operate. The entities will co-operate in a manner according to the claimed invention to generate the public parameter N in such a way that no individual entity knows the factorisation of N, and such that they can each have a share d1, d2, . . . dn respectively of the secret decryption key d where d=(d1+d2+ . . . dn)+c, where c lies between 0 and nxe2x88x921. Hence no entity will individually possess the ability to recover the plaintext message x from a ciphertext message y. Instead, all the entities must co-operate in a manner according to the claimed invention in order to decrypt the message or to generate verification data for a further entity as part of an identification and signature scheme.
This object is achieved by using the method having the features of independent claim 1 and also by using the system having the features of claim 5. In using this method and system two or more entities, having microprocessors A, B, . . . n must co-operate to generate the RSA public parameter N. Once N is determined in this way the entities can then co-operate to generate and use decryption keys to produce a decrypted output in ways dependent on the application of the communications system.
Further useful embodiments of the invention are provided for in the sub-claims.
Usefully, claim 3 provides a method of generating a high security public modulus N provided that the level of confidence that P and Q are prime is set to a sufficiently high level using primality testing algorithms well known in the art.
Particularly, claim 4 provides a method of operating a cryptographic communications system in which the entities 1, 2 . . . n must co-operate to decrypt a ciphertext message which was encrypted using the RSA type algorithm.